package com.example.leetcode;

import java.util.Arrays;

//最短无序连续子数组
public class Demo0581 {

    public static void main(String[] args) {

    }

    //排序法
    public static int findUnsortedSubarray1(int[] nums) {
        if (isSorted(nums)){
            return 0;
        }
        int[] numsSorted=new int[nums.length];
        System.arraycopy(nums,0,numsSorted,0,nums.length);
        Arrays.sort(numsSorted);

        int left=0,right=nums.length-1;
        while (nums[left]==numsSorted[left]){
            left++;
        }
        while (nums[right]== numsSorted[right]){
            right--;
        }
        return right-left+1;
    }

    public static boolean isSorted(int[] nums){
        for (int i = 0; i < nums.length-1; i++) {
            if (nums[i]>nums[i+1]){
                return false;
            }
        }
        return true;
    }


    //遍历法
    public static int findUnsortedSubarray2(int[] nums){
        int len = nums.length;
        int leftMaxValue=nums[0],right=0;
        int rightMinValue=nums[len-1],left=0;

        for (int i = 1; i < len; i++) {
            //左边区域的最大值都比右边的小 指针位置比左边区最大值小right要放指针位置
            if (leftMaxValue>nums[i]){
                right=i;
            }else {
                leftMaxValue=nums[i];
            }

            if (rightMinValue<nums[len-i-1]){
                left=len-i-1;
            }else {
                rightMinValue=nums[len-i-1];
            }
        }

        return right==0?0:right-left+1;
    }
}
